import java.util.*;

public class project {
    public int networkBecomesIdle(int[][] edges, int[] patience) {
        Map<Integer, List<Integer>> map=new HashMap<>();
        int n=patience.length;
        for(int[] edge:edges){
            List<Integer> list1=map.getOrDefault(edge[0],new ArrayList<>());
            List<Integer> list2=map.getOrDefault(edge[1],new ArrayList<>());
            list1.add(edge[1]);
            list1.add(edge[0]);
            map.put(edge[0],list1);
            map.put(edge[1],list2);
        }
        int[] arr=new int[n];
        arr[0]=-1;
        Deque<int[]> deque=new ArrayDeque<>();
        deque.addLast(new int[]{0,0});
        while (!deque.isEmpty()){
            int[] cur=deque.pollFirst();
            for(int other: map.get(cur[0])){
                if(arr[other]==0){
                    arr[other]=cur[1]+1;
                    deque.addLast(new int[]{other,cur[1]+1});
                }
            }
        }
        int ret=0;
        for(int i=1;i<n;i++){
            int x=arr[i]*2;
            int y=patience[i];
            ret=Math.max(ret,(x-1)/y*y+x);
        }
        return  ret+1;
    }
}
